class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * @author ghp
 * @title
 * @description
 */

class Solution {
    public int[] countBits(int n) {
        if (n == 0) {
            return new int[]{0};
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        // 记录已经计算过的数
        int count = 2;
        // 从n=2开始计算
        for (int i = 2; i <= n; i = count) {
            // 计算进位后的数，备注： (i+j)<=n是防止NPE
            for (int j = 0; j < i && (i+j) <= n; j++) {
                dp[i + j] = 1 + dp[j];
                count++;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.countBits(2);
    }
}

